package one.linkList;

import java.util.*;

/**
 * 还存在一点问题
 * 邻值查找：给定一个长度为 n 的序列 A，A 中的数各不相同。求：min1≤j<i|Ai−Aj|
 * 时间复杂度：
 * 思路：
 * 1）按数值排序，建立有序双链表
 * 2）映射：值索引《==》时间索引（下标索引）
 * 3）在双链表中查找前驱、后继，然后删除节点（注意：倒序删除）
 */
public class AdjacentToFind {

    Map<Integer, Integer> map_val = new HashMap<>(); //值索引
    Map<Integer, Integer> map_index = new HashMap<>(); //下标索引
    Map<Integer, Node> map_val_node = new HashMap<>(); //值索引-node节点
    List<List<Integer>> answer = new ArrayList<List<Integer>>(); //结果
    Node head = new Node(); //双向链表的保护节点


    public Node createTwoLinkedList(int[] A){ //将数组A变成一个有序双向链表
        for(int i = 0; i < A.length; i++){
            map_val.put(A[i], i);
            map_index.put(i, A[i]);
        }
        Arrays.sort(A);
        Node cur;
        Node temp = head;
        for(int i = 0; i < A.length; i++){
            cur = new Node(A[i], map_val.get(A[i]));
            temp.next = cur;
            cur.pre = temp;
            temp = cur;
            map_val_node.put(A[i], cur);
        }
        return head;
    }

    public List<List<Integer>> searchAndDelete(int[] A){
        List<Integer> list = new ArrayList<>();
        for(int i = A.length - 1; i >= 1; i--){ //倒序查找，然后删除
            int del_val = map_index.get(i);
            Node del_node = map_val_node.get(del_val); //要删除的节点
            Node pre = del_node.pre;
            Node next = del_node.next;
            if(pre == head){
                list.add(Math.abs(del_val - next.val));
                list.add(next.index + 1);
                head.next = next;
                next.pre = head;
            }else if(next == null){
                list.add(Math.abs(del_val - pre.val));
                list.add(pre.index + 1);
                pre.next = null;
            }else{
                int adjacent_pre = Math.abs(del_val - pre.val); //del_node与pre的邻值
                int adjacent_next = Math.abs(del_val - next.val); //del_node与next的邻值
                if(adjacent_pre < adjacent_next){
                    list.add(adjacent_pre);
                    list.add(pre.index + 1);//根据题意+1
                }else if(adjacent_pre > adjacent_next){
                    list.add(adjacent_next);
                    list.add(next.index + 1);
                }else {
                    list.add(adjacent_pre);
                    list.add(pre.index < next.index ? pre.index + 1 : next.index + 1);
                }
                pre.next = next;
                next.pre = pre;
            }
            for(int d : list){
                System.out.print(d + " ");
            }
            System.out.println();
            answer.add(new ArrayList<>(list)); //注意：要存副本，不然最后都会改变
            list.clear();
        }
        return answer;
    }

    public List<List<Integer>> adjacentToFind(int[] A){
        //1）按数值排序，建立有序双链表
        createTwoLinkedList(A);

        //3）在双链表中查找前驱、后继，然后删除节点（注意：倒序删除）
        return searchAndDelete(A);
    }

    public static void main(String[] args) {
        //输入
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt(); //第一行输入整数 n，代表序列长度
        int[] A = new int[n]; //长度为 n 的序列 A
        for(int i = 0; i < n; i++){
            A[i] = sc.nextInt(); //第二行输入 n 个整数A1…An,代表序列的具体数值，数值之间用空格隔开。
        }

        List<List<Integer>> answer = new AdjacentToFind().adjacentToFind(A);


        //输出
        for(int i = n - 2; i >= 0; i--){
            List list = answer.get(i);
            System.out.println(list.get(0) + " " + list.get(1));
        }

    }
}

class Node{
    public int val; //值
    public int index; //下标
    public Node pre; //前驱
    public Node next; //后继
    public Node(){}
    public Node(int val, int index){
        this.val = val;
        this.index = index;
    }
}
